def dijkstra(Adj, s, W):
    V = xrange(len(Adj))
    W = W * (len(V) - 1)
    d = [maxint] * len(V)
    #linked lists
    st = len(V) #sentinel
    prev = [st] * (len(V) + 1) 
    succ = [st] * (len(V) + 1)
    head = [st] * W 
    
    pi = [None] * len(V)
    done = ['no'] * len(V)
    d[s] = 0

    head[0] = s
    prev[s] = st
    succ[s] = st
    cur = 0
    
    while True:
        while cur < W and head[cur] == st:
            cur += 1
        if cur >= W: break
        #extract
        u = head[cur]
        head[cur] = succ[u]
        succ[prev[u]] = succ[u]
        prev[succ[u]] = prev[u]
        if done[u] == 'yes': continue
        done[u] = 'yes'
        for (v, w) in Adj[u]:
            if done[v] == 'no':
                if d[v] > d[u] + w:
                    if d[v] < maxint and head[d[v]] == v:
                        head[d[v]] = succ[v]
                    d[v] = d[u] + w
                    pi[v] = u
                    #delete from old
                    succ[prev[v]] = succ[v]
                    prev[succ[v]] = prev[v]
                    #insert into new
                    h = head[d[v]]
                    p = prev[h]
                    succ[v] = h
                    prev[v] = p
                    succ[p] = v
                    prev[h] = v
                    head[d[v]] = v
    return pi, d

if __name__=='__main__':
    from heapq import heappush, heappop
    from sys import maxint
    from pprint import pprint
    Adj = [[(1,10),(2,5)],[(2,2),(3,1)],[(1,3),(3,9),(4,2)],[(4,4)],[(3,6),(0,7)]] #CLRS pp.595
    print 'Adj: Adj[u] stores (v,w[u,v])'
    pprint(Adj)
    pi, d = dijkstra(Adj, s=0, W=10)
    print 'Pi:', pi
    print 'd :', d
